/*
*线性表，vs2010编译
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define elementType int 	//用宏定义定义一个int类型的别名，当处理elementType的时候都用int替换，方便处理不同类型的数据，例如可以换成double
//定义线性表的结构体
typedef struct
{
	int usedLength;	//使用过的空间个数
	int maxLength;	//申请的最大的空间
	elementType *elem;	//一个指针，指向malloc申请到的空间首地址，即线性数据的首地址
} Sqlist;
//end，这个数据结构用来记录表的属性
int ifSuccess(int );	//根据参数判断是否执行成功，根据函数的返回值进行判断
Sqlist createNewList();	//创建新的线性表，返回值为线性表（结构体）
int initElement(Sqlist *);	//初始化线性表，将一整行数据记录入表中
int setElement(int ,elementType,Sqlist *);	//将指定位置的元素设为给定的值
int insertAElement(int ,elementType ,Sqlist *);	//插入一个数据
int printAllElement(Sqlist *);	//打印所有的数据
int deleteElement(int ,Sqlist *);	//删除数据
int enlargeList(Sqlist *);	//扩充线性表的长度
int findElement(elementType,Sqlist *);	//查找元素在线性表中的位置
elementType findId(int ,Sqlist *);	//查找指定位置的元素的值
int deleteList(Sqlist *);	//删除表
int ifListExist(Sqlist *);	//检查表是否存在
int emptyAList(Sqlist *);	//清空表
elementType qian(int ,Sqlist *);	//求前驱
elementType hou(int ,Sqlist *);	//求后驱
int leng(Sqlist *);			//求表的长度
elementType deleteElementAndReturnit(int ,Sqlist *);	//删除指定元素并将这个元素的值返回

int main(int argc,char *argv[])
{
	int i = 0,sti = 0,error = 1;	//i为操作数，sti标记表是否创建，error为错误检测
	while(0 <= i && i <= 14)	//限制操作数的范围
	{
		printf("------------\n");
		printf("线性表操作：\n");
		printf("1 创建一个新表\n");
		printf("2 销毁一个表\n");
		printf("3 向空表中添加一系列元素\n");
		printf("4 从表中删除指定位置的元素\n");
		printf("5 在表中添加一个元素\n");
		printf("6 从表中查找指定位置的元素\n");
		printf("7 查找元素在表中的位置\n");
		printf("8 检查表是否存在\n");
		printf("9 打印表中的所有元素\n");
		printf("10清空线性表\n");
		printf("11求前驱\n");
		printf("12求后驱\n");
		printf("13求线性表的长度\n");
		printf("14 从表中删除指定位置的元素并返回该元素\n");
		int id = -1;	//id为元素的位置信息，初始化为非法值
		Sqlist list;	//创建一个空的线性表结构体
		if(!scanf("%d",&i))	//判断输入是否有误，scanf输入成功的返回值为true
		{
			printf("输入错误\n");
			error = 0;	//error在下文用到，为零表示错误
			getchar();	//吃掉类型不符的字符，上面的scanf在遇到类型不符的字符时并不处理
		}else
		{
			error = 1;	//没有错误
		}
		if(sti)	//若sti不为零，sti初始化为0，第一次操作不执行if里面的语句，因为表还没有创建，当表被删除后同样不能对表操作
		{
			switch(i)
			{
				case 1:
				printf("线性表已创建\n");	//线性表的创建是第一位的，所有的操作都在线性表创建后，所以创建放在下文中
				break;
				case 2:
				printf("销毁一个表\n");
				ifSuccess(deleteList(&list));
				sti = 0;	//标记表已经删除，用户不能再对表中的内容操作
				break;
				case 3:
				printf("向空表中添加一系列元素,空格隔开，ctrl^d结束\n");
				ifSuccess(initElement(&list));
				break;
				case 4:
				printf("从表中删除一个元素\n请输入元素在表中的位置");
				scanf("%d",&id);
				ifSuccess(deleteElement(id,&list));
				break;
				case 5:
				printf("在表中添加一个元素\n请输入元素在表中的位置");
				scanf("%d",&id);
				elementType element1;
				printf("请输入元素\n");
				scanf("%d",&element1);
				ifSuccess(insertAElement(id,element1,&list));
				break;
				case 6:
				printf("从表中查找指定位置的元素\n");
				scanf("%d",&id);
				printf("%d\n",findId(id,&list));
				break;
				case 7:
				printf("查找元素在表中的位置\n");
				elementType element2;
				scanf("%d",&element2);
				printf("%d\n",findElement(element2,&list));
				break;
				case 8:
				printf("检查表是否存在\n");
				if(ifListExist(&list))
				{
					printf("线性表已创建\n");
				}else
				{
					printf("线性表不存在！\n");
				}
				break;
				case 9:
				printf("打印表中的所有元素\n");
				ifSuccess(printAllElement(&list));
				break;
				case 10:
				printf("清空线性表\n");
				ifSuccess(emptyAList(&list));
				break;
				case 11:
				printf("求前驱\n请输入元素的位置");
				scanf("%d",&id);
				printf("前驱为%d\n",qian(id,&list));
				break;
				case 12:
				printf("求后驱\n请输入元素的位置");
				scanf("%d",&id);
				printf("后驱为%d",hou(id,&list));
				break;
				case 13:
				printf("求表的长度\n");
				printf("长度为%d",leng(&list));
				break;
				case 14:
				printf("从表中删除指定位置的元素并返回该元素\n请输入元素的位置：");
				scanf("%d",&id);
				printf("该元素为%d\n",deleteElementAndReturnit(id,&list));
				break;
				default:
				printf("输入错误\n");
				sti = 0;	//将身体sti置为零，避免用户进行if里面的操作
				break;
			}
		}else if(error)	//如果error不为零，也就是输入的数据类型没有错误；且sti为零，表示还没创建表（上文的if条件）
		{
			if(i != 1) printf("表还没有创建，请先创建一个表\n"); //如果用户还没有创建表就对表的内容操作，则提示
			printf("创建一个线性表\n");
			list = createNewList();		//对表赋值，这里分配了存储空间
			sti = 1;					//标记表已经创建，可以执行对表的操作了
			printf("线性表已创建\n");
		}
		system("pause");	//让while循环暂停
		system("cls");		//清屏
	}
	system("pause");		//在程序结束前暂停
	return 0;
}

int ifSuccess(int s)	//根据参数的值输出提示信息
{
	if(s == 0)
	{
		printf("--操作成功--\n");
	}else
	{
		return s;
	}
	return 0;
}

Sqlist createNewList()
{
	Sqlist list;
	list.usedLength = 0;	//初始化结构体中的数据，使用过的空间为零
	list.maxLength = 100;	//申请的空间为100
	list.elem = (elementType *)malloc(sizeof(elementType)*list.maxLength);	//为elem申请空间
	return list;	//返回结构体
}

int initElement(Sqlist *list)	//不断向表尾部加入数据
{
	int start = 0;
	elementType element;
	while(scanf("%d",&element))	//当能够正确读入数据时，不断读入数据，直到错误发生(类型不符合，比如字母)
	{
		if(start == list -> maxLength)	//当线性表长度不够时进行扩充
		{
			if(enlargeList(list) != 0)	//enlargeList()在下文有定义
			{
				printf("扩充线性表失败，程序退出\n");
				return -1;
			}
		}
		list -> elem[start] = element;	//将当前读取的元素放置在累加的start编号位置上
		list -> usedLength ++;	//使用过的空间加一
		start ++;	//编号向后推进
	}
	getchar();	//当scanf()遇到类型不符合的输入时，返回false，退出while循环，剩下那个类型不符合的字符由getchar()吃掉，等于清空输入缓缓冲区，防止干扰下文的输入
	return 0;
}

int insertAElement(int id,elementType element,Sqlist *list)	//在已经有数据的表的位置插入数据
{
	int i;
	if(id >= 0 && id <= list -> usedLength)	//判断插入的位置是否合适
	{
		if(id == list -> maxLength)	//若插入的位置刚好在表尾且表中剩余空间已满，则扩充表
		{
			if(enlargeList(list) != 0)
			{
				printf("扩充线性表失败，程序退出\n");
				return -1;
			}
		}
		for(i = list -> usedLength;i > id;i --)	//将插入位置后的元素依次后移一位(从尾部开始)
		{
			list -> elem[i] = list -> elem[i - 1];
		}
		list -> elem[id] = element;	//将插入的位置的数据换成需要插入的数据
			list -> usedLength ++;	//表的长度加一
			return 0;	//成功返回0
	}else
	{
		return 1;	//若不符合条件则退出，并返回1表示出错
	}
}

int setElement(int id,elementType element,Sqlist *list)	//替换表中已存在的元素
{
	if(id >= 0 && id < list -> usedLength)
	{
		list -> elem[id] = element;
		return 0;
	}else
	{
		return 1;
	}
	return 0;
}

int printAllElement(Sqlist *list)	//打印所有的元素
{
	int i;
	for(i = 0;i < list -> usedLength;i ++)	//将编号一次向后推进并打印
	{
		printf("%d ",list -> elem[i]);
	}
	return 0;
}

int deleteElement(int id,Sqlist *list)	//删除一个元素
{
	if(id >= 0 && id < list -> usedLength)	//判断元素的位置是否正确
	{
		int i;
		for(i = id;i < list -> usedLength - 1;i ++)	//从给定的位置依次向前覆盖
		{
			list -> elem[i] = list -> elem[i + 1];
		}
		list -> usedLength --;	//表的长度减一
	}else
	{
		return 1;
	}
	return 0;
}

elementType deleteElementAndReturnit(int id,Sqlist *list)	//删除一个元素并且返回这个元素
{
	elementType tmp = list -> elem[id];	//先记录下这个元素的值
	if(id >= 0 && id < list -> usedLength)
	{
		int i;
		for(i = id;i < list -> usedLength - 1;i ++)
		{
			list -> elem[i] = list -> elem[i + 1];
		}
		list -> usedLength --;
	}else
	{
		printf("输入错误");
		return -1;
	}
	return tmp;	//返回被删除的元素的值
}

elementType qian(int id,Sqlist *list)
{
	if(0 < id && id <= list -> usedLength)
	{	return list -> elem[id -1];
	}else{
	return -1;
	}
}

elementType hou(int id,Sqlist *list)	//求后驱
{
	if(0 <= id && id <= list -> usedLength - 1)
	{	return list -> elem[id + 1];
	}else{
	return -1;
	}
}

int leng(Sqlist *list)	//求前驱
{
	return list -> usedLength;
}

int enlargeList(Sqlist *list)	//扩充线性表的存储空间
{
	list -> elem = (elementType *)realloc(list -> elem,sizeof(elementType)*(list -> maxLength + 100));
	if(list -> elem == NULL)	//如果扩充失败，则list -> elem的值为NULL
	{
		return -1;
	}else
	{
		list -> maxLength += 100;	//扩充成功
	}
	return 0;
}	

int findElement(elementType find,Sqlist *list)	//查找元素在表中的位置
{
	int i;
	for(i = 0;i < list -> usedLength;i ++)
	{
		if(list -> elem[i] == find)
		{
			return i;
		}
	}
	return -1;
}

elementType findId(int id,Sqlist *list)	//查找id位置的元素的值并返回
{
	return list -> elem[id];
}

int deleteList(Sqlist *list)	//删除表
{
	if(list -> maxLength != 0)
	{
		free(list -> elem);	//删除表中elem指针指向的内存空间
		list -> elem = NULL;
		list -> usedLength = 0;
		list -> maxLength = 0;
		return 0;
	}else
	{
		return 1;
	}
	return 1;
}

int emptyAList(Sqlist *list)	//清空表，不清空内存空间
{
	if(list -> maxLength != 0)
	{
		//free(list -> elem);
		list -> elem = NULL;
		list -> usedLength = 0;
		list -> maxLength = 0;
		return 0;
	}else
	{
		return 1;
	}
	return 1;
}

int ifListExist(Sqlist *list)	//检查表是否存在
{
	if(list -> maxLength != 0)
	{
		return 1;
	}else
	{
		return 0;
	}
	return 0;

}